/**
 * @author Maewa
 * @version 1.0
 * 
 * Given two lists (can also be arrays or sets), you need to retrieve
 * the common elements between them. I see three ways of doing it.
 * 
 */

package com.maewa.cisco.uniquelist;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class UniqueList {
	public static void main(String[] args) {
		List<Integer> list1 = new ArrayList<Integer>();
		list1.add(1);
		list1.add(2);
		list1.add(9);
		list1.add(5);
		list1.add(59);
		
		List<Integer> list2 = new ArrayList<Integer>();
		list2.add(1);
		list2.add(3);
		list2.add(58);
		list2.add(9);
		list2.add(10);
		
		method1(list1, list2);
		method2(list1, list2);
		method3(list1, list2);
	}

	/**
	 *  Simple method, but too many iterations - for every element in 
	 *  list1, we might end up iterating list2 once
	 */
	private static void method1(List<Integer> list1, List<Integer> list2) {
		List<Integer> commonList = new ArrayList<Integer>();
		
		for(Integer i : list1) {
			if(list2.contains(i)) {
				commonList.add(i);
			}
		}
		
		System.out.println(commonList.toString());
	}
	
	/**
	 * In this method, both the lists are iterated only once, but we might
	 * have iterations while sorting
	 */
	private static void method2(List<Integer> list1, List<Integer> list2) {
		Collections.sort(list1);
		Collections.sort(list2);
		
		List<Integer> commonList = new ArrayList<Integer>();
		int i = 0, j = 0;
		
		while(i < list1.size() && j < list2.size()) {
			if(list1.get(i) < list2.get(j)) {
				i++;
			} else if (list1.get(i) > list2.get(j)) {
				j++;
			} else {
				commonList.add(list1.get(i));
				i++;
				j++;
			}
		}
		
		System.out.println(commonList.toString());
	}
	
	/**
	 * Efficient and easy method without iterations (however, retain method might
	 * have some internal iterations)
	 */
	private static void method3(List<Integer> list1, List<Integer> list2) {
		Set<Integer> s1 = new HashSet<Integer>(list1);
		Set<Integer> s2 = new HashSet<Integer>(list2);
		
		s1.retainAll(s2);
		
		System.out.println(s1);
	}
}
